Bit disposal is the process of eliminating undesired bits in a binary number in a way that has some desirable numerical property. Truncation is the most common way of disposing of bits, which are typically located to the right of a binary point in a binary number. Pure truncation, the simple removal of bits beyond a certain point in a binary number, always results in an error, in that part of the number is lost. In addition to the error, pure truncation is biased, in that the resulting number is always smaller or equal to the original number, resulting in a negative bias. Numbers are truncated to remove unwanted bits, such as are present after multiplication or division operation.
For instance, and noe using decimal numbers as an example to facilitate the discussion, if a number such as 6.75 is truncated to an integer value, the value is 6. After several such numbers have been truncated and arithmetically combined, the resulting number may be significantly smaller than the number which would have been derived had truncation not occurred. With pure truncation, it does not matter whether the original number is 6.005 or 6.995, the truncated value is 6. The following table depicts the results of bit disposal using pure truncation, wherein it is assumed that truncation takes place at the binary point:
TABLE 1 ______________________________________ Original Number Truncated Number Error ______________________________________ 111 11 -.1 110 11 .0. 101 10 -.1 100 10 .0. 011 01 -.1 010 01 .0. 001 00 -.1 000 00 .0. .uparw. binary point ______________________________________
In the context of computer manipulation, pure truncation is a very efficient technique in that it requires no additional hardware. The resulting error, however, is quite large, and the bias is that the truncated number is always equal to or smaller than the actual number. Additionally, the bias is always negative. As used herein, +ve indicates a positive bias, while -ve indicates a negative bias.
Another technique for truncating a number is called rounding. In the case of rounding, the value of the number portion being retained is examined and either retained or increased to the next incremental retained value, depending on whether or not the portion being discarded is equal to or greater than, typically, one-half the incremental value. The results of rounding are less error prone than in pure truncation, however, over a long series of operations, rounding becomes biased because the break point between selecting the next higher or retaining the lower value is always rounded in favor of either higher or lower. In the usual case of rounding up those values which are precisely one-half of the value between the increments, the bias becomes positive over time. The following table illustrates the error and bias associated with traditional rounding techniques:
TABLE 2 ______________________________________ Original Number Rounded Number Error Bias ______________________________________ 3.758 3.76 +.02 +ve 4.234 2.23 -.04 -ve 5.355 5.36 +.05 +ve 1.333 1.33 -.03 -ve 7.897 7.90 +.03 +ve 8.335 8.34 +.05 +ve ______________________________________
Of the six numbers shown, two are rounded up less than 0.05, two are rounded down less than 0.05, and two are rounded up by exactly 0.05, resulting in four of the six roundings having a positive bias.
The bias in rounding may be eliminated by the symmetric pairing of positive and negative biases for any collection of numbers. However, hardware is required to analyze the incremental steps in a number series. Such a variation of rounding is called round to even or R*. In R* rounding, the one-half values are, as much as possible, symmetrically evenly rounded up and down. Assuming that each rounding, up or down, is equally likely, and that positive and negative errors offset one another, bias is virtually eliminated, assuming all cases are equally likely, and a small error variance results. However, the provision of the required hardware, which at a minimum is a separate adder, is expensive in terms of overall architecture design.
Another form of truncation is called jamming, or von Neumann rounding. In the case of binary numbers, whenever a bit is discarded, a "one" is "jammed" into the least significant bit (LSB) of the remaining number. This technique requires very little hardware, but induces the same total bias as does rounding, although it requires no more time than pure truncation. The error variance induced by jamming is larger than that with truncation because a "one" is always placed in the least significant bit, regardless of the value of the truncated bit. Examples of "jammed" numbers are given in Table 3:
TABLE 3 ______________________________________ Original Number Truncated Number Error ______________________________________ 111 11 -.1 110 11 .0. 101 11 +.1 100 11 +.1 011 01 .0. 010 01 .0. 001 01 +.1 000 01 +.1 .uparw. binary point ______________________________________
Digital computers are equally sensitive to bias as they are to absolute error variance values. Neural network computers, however, are much more sensitive to bias than they are to absolute error values. It is desirable, therefore, to provide a bit disposal apparatus and technique which is as bias free as possible. Because neural network computers are small in terms of total circuitry, such a disposal technique must also be small, i.e., require little hardware.